package radix;

public class Radix01 {
    public static void sort(int[] arr){
        //求最高位数
        int max = 0;
        int min = 0;
        for (int i : arr) {
            if (i > max)max = i;
            if (i < min)min = i;
        }
        int digit = 1;
        while(max / 10 > 0){
            max /= 10;
            digit++;
        }
        //开始基数排序
        for (int i = 1; i <= digit; i++) {
            int[] count = new int[10];
            int[] result = new int[arr.length];
            //求每次该和多少取余
            int times = 1;
            for(int j = 1;j < i; j++){
                times *= 10;
            }
            for (int k = 0; k < arr.length; k++) {
                count[(arr[k]/times)%10]++;
            }
            for (int l = 1; l < count.length; l++) {
                count[l] += count[l-1];
            }
            for (int m = arr.length - 1; m >= 0 ; m--) {
                result[--count[(arr[m]/times)%10]] = arr[m];
            }
            System.arraycopy(result,0,arr,0,arr.length);
        }
    }
}
